1. Field of the Invention
The present invention relates to a motion estimator, particularly to a motion estimator employing a three-step hierarchical search block-matching algorithm, wherein only two memory blocks, as opposed to three with conventional motion estimators, are required.
2. Description of the Related Art
Video applications have been widely used in recent years. Imaging and video compressing technologies have played a pivotal role in modern communication and storage media. Consumer electronic products, such as videophone, video conferencing, high-resolution digital television (HDTV) and random access video, all employ data compression technology to minimize data volume for transmission and storage, and to render a higher picture quality in relation to the input/output bandwidth. Motion estimators are used for compression in current video compression standards such as H.263, MPEG-1 and MPEG-2, to minimize redundancy between frames. Therefore, a fast and efficient motion estimator will enhance video compression technology. Particularly, the tremendous growth in data volume in applications such as HDTV indicates that a high-geared calculation-intensive motion estimator will be required in the future.
Block matching is often performed in motion estimation. The "Full Search", which finds the correct locations of the blocks and obtains better picture quality, is time-consuming and calculation-intensive. Faster methods are therefore developed to eliminate the disadvantages associated with the Full Search. Among them, the Three-Step Hierarchical Search Block-Matching Algorithm is most widely used, although the picture quality obtained therewith is degraded compared to that obtained with the Full Search. However the operation load is reduced to only about one-tenth of the load of the Full Search.
In a one-dimensional three-step hierarchical search block-matching framework, candidate blocks are stored in registers; whereas in two-dimensional three-step hierarchical search block-matching, such as "Parallel architecture for 3-step hierarchical search block-matching algorithm" proposed by H. M. Jong, L. G. Chen, and T. D. Chiueh in IEEE Trans. Circuits Syst. Video Technol. (Vol. 4, no. 4, pp.407-416, Aug. 1994), the candidate blocks are stored in the static random access memory (SRAM), which is smaller in size than registers and is accessed with memory interleaving. This algorithm yields a higher throughput but with the drawback that the SRAM has to store a data volume 1.5 times greater than that of the candidate blocks to maintain the sought after throughput.
FIG. 1 (Prior Art) is a diagram illustrating the memory layout of a conventional three-step hierarchical search block-matching motion estimator using memory interleaving, wherein C.sub.n denotes a current block of 16.times.16 and the corresponding candidate blocks B.sub.n are placed in P.sub.0 and P.sub.1 in an interleaving manner. Each of the two memory blocks P.sub.0 and P.sub.1 is one half of the size of the candidate block B.sub.n. While block-matching is being performed in block C.sub.n, the corresponding section of the candidate block B.sub.n+1 of the next current block C.sub.n+1 has to be stored in advance in the memory block P.sub.2, which is also one half of the size of the candidate block B.sub.n (B.sub.n+1). Therefore, when block-matching of C.sub.n is completed, block-matching of C.sub.n+1 can be performed immediately. In this case, the corresponding candidate block of block C.sub.n+1 is already stored in memory blocks P.sub.1 and P.sub.2 and the data stored in the memory block P.sub.0 are no longer needed, thereby freeing up memory block P.sub.0 for storing the candidate block B.sub.n+2 of the current block C.sub.n+2 in advance.
In this framework, a memory block needs to store 30.times.16 (.about.10.5K) bits of data (that is about one half of the candidate block), hence three memory block are required to store 1.5 K bits of data. This will take up approximately one half of the size (area) of the hardware. Consequently, a reduction in memory blocks will significantly reduce the size of the required hardware components.